Conventionally, a cache used for rapid access to recently used data uses a Least Recently Used (LRU) algorithm. In the LRU cache, whether a desired data item is present in the cache is determined by reference to a hash table. If a desired data item is found in the cache (cache hit), the LRU value of the data item to the current LRU count. More specifically, because the LRU cache is sorted by LRU value, the cache hit data item is moved from the existing spot in the cache to the top of the cache.
If a desired data item is not in the cache, i.e., a cache miss, the data item is retrieved from a storage device for use by the requesting application, and the data item is also added to the top of the cache (i.e., assigned current LRU value). The oldest data item (lowest LRU value) is evicted from the bottom of the cache.
The LRU cache is commonly used because it is relatively easy to implement. However, the LRU cache becomes polluted with a sequential scan. Further, the LRU cache cannot take advantage of multi-core processing. Moreover, the LRU cache requires substantial CPU overhead in the case of a cache hit, and it requires a large amount of memory to maintain cache entries ordered by the LRU value.
Another known cache algorithm is the Low Inter-reference Recency Set (LIRS), which uses a modified LRU cache and is more resistant to being polluted by a sequential scan compared to the basic LRU cache. However, LIRS is more complex to implement compared to the basic LRU cache, and therefore has a higher CPU overhead. LIRS also has higher memory usage overhead for a cache hit, and cannot take advantage of multi-core processing.
Another known cache algorithm is the Adaptive Replacement Cache (ARC) from IBM. However, ARC is also more complex to implement compared to the basic LRU cache, and therefore ARC also has a relatively high CPU overhead. The ARC also has a relatively high memory usage overhead for a cache hit, and cannot take advantage of multi-core processing.
Another known cache algorithm is 2Q, first described in a VLDB conference paper in 1994. The 2Q algorithm is scan friendly and relatively easy to implement. However, 2Q requires relatively high memory usage, and cannot take advantage of multi-core processing.
Another known cache algorithm is Clock, which approximates LRU but has low CPU overhead on cache hit and can take advantage of multi-core processing. However, it shares the same problem as LRU in that a sequential scan pollutes the cache.
Another known cache algorithm is ClockPro, which approximates LIRS but has low CPU overhead on cache hit and can take advantage of multi-core processing. However, it is more complex to implement.
Another known cache algorithm is Clock with Adaptive Replacement (CAR), which approximates ARC but has low CPU overhead on cache hit and can take advantage of multi-core processing. However, it is more complex to implement.
What is desired is a cache algorithm that is scan friendly, is relatively easy to implement, has low CPU overhead on cache hit, can take advantage of multi-core processing, and does not require a high memory usage.